package LeetCode;

import java.util.*;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}17:03
 */
public class LeetCode347 {
    public int[] topKFrequent(int[] nums, int k) {

//        Queue<Integer> queue = new PriorityQueue<>();
//        Map<Integer,Integer> map = new HashMap<>();
//        for (int i = 0; i < nums.length; i++){
//            map.put(nums[i],map.get(nums[i])+1);
//        }
//
//        if ( k > nums.length){
//            return new int[]{};
//        }
//
//        queue
        //进行一个频率的记录
        Map<Integer,Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else {
                map.put(num,1);
            }
        }

        //遍历map，用最小堆保存频率最大的k个元素 指定排序规则
        Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
            return map.get(o1) - map.get(o2);
        });

//        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer a, Integer b) {
//                return map.get(a) - map.get(b);
//            }
//        });

        for (Integer key : map.keySet()) {
            if (queue.size() < k){
                queue.add(key);
            }else if (map.get(key) > map.get(queue.peek())){// 这是最小堆队顶的数字，比这个大就可以入队列然后删掉原来的
                queue.poll();
                queue.add(key);
            }
       }
        //取出最小堆的元素
        int[] res = new int[k];
        int index = 0;
        while (!queue.isEmpty()) {
            res[index] = queue.poll();
            index++;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new LeetCode347().topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2)));
    }
}
